package leetbook.graph;

import java.util.ArrayList;
import java.util.Stack;

public class Solution210 {

    //bfs
    public int[] findOrder1(int numCourses, int[][] prerequisites) {
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>(); //邻接链表
        int[] indegree = new int[numCourses]; //记录入度
        for (int i = 0; i < numCourses; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] cp: prerequisites) {
            adj.get(cp[1]).add(cp[0]);
            indegree[cp[0]]++;
        }
        //2，找入度为0的点开始
        int[] res = new int[numCourses]; //存放拓扑排序结果
        int count = 0; //记录已排序顶点数
        Stack<Integer> deg0Vert = new Stack<>(); //保存当前入度0的节点
        for (int i = 0; i < numCourses; i++) {
            if(indegree[i]==0) deg0Vert.push(i);
        }
        while (!deg0Vert.isEmpty()){
            int vert = deg0Vert.pop();
            res[count++] = vert;
            //vert相邻节点入度都-1
            for (int v: adj.get(vert)) {
                if(--indegree[v]==0) deg0Vert.push(v);
            }
        }
        if(count<numCourses) return new int[0];
        return res;
    }

    //dfs
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        //1.构建邻接链表和入度数组
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>(); //邻接链表
        for (int i = 0; i < numCourses; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] cp: prerequisites) {
            adj.get(cp[1]).add(cp[0]);
        }
        //2.dfs
        int[] status = new int[numCourses];
        Stack<Integer> stack = new Stack<>();
        boolean flag = true; //发现有环就停止
        for (int i = 0; i < numCourses; i++) {
            flag &= dfs(adj,status,i,stack);
            if(!flag) return new int[0];
        }
        //stack中保存的是拓扑排序的逆序
        int[] res = new int[numCourses];
        int count = 0;
        while (!stack.empty()){
            res[count++] = stack.pop();
        }
        return res;
    }

    public boolean dfs(ArrayList<ArrayList<Integer>> adjLink, int[] status, int curNode, Stack<Integer> stack){
        if(status[curNode]==1) return false;
        if(status[curNode]==-1) return true;
        status[curNode] = 1;
        boolean flag = true;
        for (int v: adjLink.get(curNode)) {
            flag &= dfs(adjLink,status,v,stack);
            if(!flag) break;
        }
        //发现环
        if(!flag) return false;
        //相邻节点没有环
        status[curNode] = -1;
        stack.push(curNode);
        return true;
    }
}
